package com.dmall.sort;

import com.dmall.sort.enums.OrderByTypeEnum;
import com.dmall.sort.enums.SortTypeEnum;
import com.sun.org.apache.xpath.internal.operations.Or;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Stack;

/**
 * 排序算法工具类
 * @author xiao1.wang@dmall.com
 * @date 2019-07-18 18:35:14
 */
public class SortAlgorithmUtils {

    public static void main(String[] args) throws Exception {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8, 3};
        System.out.println("排序前：" +Arrays.toString(arr));
        // bubbleSort(arr, OrderByTypeEnum.ASC);
        // selectionSort(arr, OrderByTypeEnum.DESC);
        // insertionSort(arr, OrderByTypeEnum.DESC);
        // shellSort(arr, OrderByTypeEnum.ASC);
        // shellSortImprove(arr, OrderByTypeEnum.ASC);
        // quickSort(arr, OrderByTypeEnum.DESC);
        // quicklySort(arr, OrderByTypeEnum.DESC);
        quickSortNonRecursion(arr, OrderByTypeEnum.ASC);
        System.out.println("排序后：" + Arrays.toString(arr));

        /*Random random = new Random();
        Integer arrLength = 80;
        Integer[] arr = new Integer[arrLength];
        for (int i = 0; i < arrLength; i++) {
            arr[i] = random.nextInt(200000);
        }*/

        //System.out.println("排序前：" + Arrays.toString(arr));
        //SortTypeEnum sortType = SortTypeEnum.QUICK_SORT;
        //double time = testSort1(arr, sortType, OrderByTypeEnum.ASC);
        //System.out.println(sortType.getDesc() + ": time = " + time);
        //System.out.println("排序后：" + Arrays.toString(arr));
    }

    /**
     * 通过反射的方式测试排序方法的性能
     * @param arr           要排序的数组
     * @param sortType      排序类型枚举 {@link SortTypeEnum}
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组元素的泛型
     * @return              排序所需要的时间
     */
    public static <E extends Comparable<E>> double testSort(E[] arr, SortTypeEnum sortType, OrderByTypeEnum orderByType) {
        long start = System.nanoTime();
        if (sortType.equals(SortTypeEnum.BUBBLE_SORT)) {
            start = System.nanoTime();
            bubbleSort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.SELECTION_SORT)) {
            start = System.nanoTime();
            selectionSort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.INSERTION_SORT)) {
            start = System.nanoTime();
            insertionSort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.SHELL_SORT)) {
            start = System.nanoTime();
            shellSort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.SHELL_SORT_IMPROVE)) {
            start = System.nanoTime();
            shellSortImprove(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.QUICK_SORT)) {
            quickSort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.QUICKLY_SORT)) {
            quicklySort(arr, orderByType);
        } else if (sortType.equals(SortTypeEnum.QUICK_SORT_NON_RECURSION)) {
            quickSortNonRecursion(arr, orderByType);
        }
        long end = System.nanoTime();
        return (end - start) / 1000000000.0;
    }

    /**
     * 通过反射的方式测试排序方法的性能
     * @param arr           要排序的数组
     * @param sortType      排序类型枚举 {@link SortTypeEnum}
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组元素的泛型
     * @return              排序所需要的时间
     * @throws Exception    抛出的异常
     */
    public static <E extends Comparable<E>> double testSort1(E[] arr, SortTypeEnum sortType, OrderByTypeEnum orderByType) throws Exception {
        Class<SortAlgorithmUtils> clazz = SortAlgorithmUtils.class;
        Method method = clazz.getMethod(sortType.getMethodName(), Comparable[].class, orderByType.getClass());
        long start = System.nanoTime();
        method.invoke(null, arr, orderByType);
        long end = System.nanoTime();
        return (end - start) / 1000000000.0;
    }

    /**
     * 冒泡排序
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void bubbleSort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        boolean isSwap = false;
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            // 默认为升序
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j].compareTo(arr[j + 1]) > 0) {
                        isSwap = true;
                        swap(arr, j, j + 1);
                    }
                }
                if (!isSwap) {
                    break;
                } else {
                    isSwap = false;
                }
            }
        } else {
            // 降序
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j].compareTo(arr[j + 1]) < 0) {
                        isSwap = true;
                        swap(arr, j, j + 1);
                    }
                }
                if (!isSwap) {
                    break;
                } else {
                    isSwap = false;
                }
            }
        }
    }

    /**
     * 选择排序
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void selectionSort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            for (int i = 0; i < arr.length - 1; i++) {
                int minIndex = i;
                E min = arr[i];
                for (int j = i + 1; j < arr.length; j++) {
                    if (min.compareTo(arr[j]) > 0) {
                        minIndex = j;
                        min = arr[j];
                    }
                }
                swap(arr, i, minIndex);
            }
        } else {
            for (int i = 0; i < arr.length - 1; i++) {
                int maxIndex = i;
                E max = arr[i];
                for (int j = i + 1; j < arr.length; j++) {
                    if (max.compareTo(arr[j]) < 0) {
                        maxIndex = j;
                        max = arr[j];
                    }
                }
                swap(arr, i, maxIndex);
            }
        }
    }

    /**
     * 插入排序
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void insertionSort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        E insertVal = null;
        int insertIndex = 0;
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            for (int i = 1; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i - 1;
                while (insertIndex >= 0 && insertVal.compareTo(arr[insertIndex]) < 0) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex --;
                }
                if (insertIndex + 1 != i) {
                    arr[insertIndex + 1] = insertVal;
                }
            }
        } else {
            for (int i = 1; i < arr.length; i++) {
                insertVal = arr[i];
                insertIndex = i - 1;
                while (insertIndex >= 0 && insertVal.compareTo(arr[insertIndex]) > 0) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex --;
                }
                if (insertIndex + 1 != i) {
                    arr[insertIndex + 1] = insertVal;
                }
            }
        }
    }

    /**
     * 希尔排序
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void shellSort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int half = 2;
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            for (int gap = arr.length / half; gap > 0; gap /= half) {
                for (int i = gap; i < arr.length; i++) {
                    // 遍历各组中所有的元素(共gap组，每组有(arr.length/gap)个元素), 步长gap
                    for (int j = i - gap; j >= 0; j -= gap) {
                        // 如果当前元素大于加上步长后的那个元素，说明交换
                        if (arr[j].compareTo(arr[j + gap]) > 0) {
                            swap(arr, j, j + gap);
                        }
                    }
                }
            }
        } else {
            for (int gap = arr.length / half; gap > 0; gap /= half) {
                for (int i = gap; i < arr.length; i++) {
                    // 遍历各组中所有的元素(共gap组，每组有(arr.length/gap)个元素), 步长gap
                    for (int j = i - gap; j >= 0; j -= gap) {
                        // 如果当前元素大于加上步长后的那个元素，说明交换
                        if (arr[j].compareTo(arr[j + gap]) < 0) {
                            swap(arr, j, j + gap);
                        }
                    }
                }
            }
        }
    }

    /**
     * 希尔排序的改进版
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void shellSortImprove(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int half = 2;
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            for (int gap = arr.length / half; gap > 0; gap /= half) {
                // 从第gap个元素，逐个对其所在的组进行直接插入排序
                for (int i = gap; i < arr.length; i++) {
                    int j = i;
                    E temp = arr[j];
                    while (j - gap >= 0 && temp.compareTo(arr[j - gap]) < 0) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        } else {
            for (int gap = arr.length / half; gap > 0; gap /= half) {
                // 从第gap个元素，逐个对其所在的组进行直接插入排序
                for (int i = gap; i < arr.length; i++) {
                    int j = i;
                    E temp = arr[j];
                    while (j - gap >= 0 && temp.compareTo(arr[j - gap]) > 0) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void quickSort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1, orderByType);
    }

    /**
     * 快速排序递归方法
     * @param arr
     * @param left
     * @param right
     * @param orderByType
     * @param <E>
     */
    private static <E extends Comparable<E>> void quickSort(E[] arr, int left, int right, OrderByTypeEnum orderByType) {
        int l = left;
        int r = right;
        E pivot = arr[(left + right) / 2];
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            while (l < r) {
                while (arr[l].compareTo(pivot) < 0) {
                    l ++;
                }

                while (arr[r].compareTo(pivot) > 0) {
                    r --;
                }

                if (l >= r) {
                    break;
                }

                // exchange
                swap(arr, l, r);

                if (arr[l].compareTo(pivot) == 0) {
                    r --;
                }

                if (arr[r].compareTo(pivot) == 0) {
                    l ++;
                }

                if (l == r) {
                    l ++;
                    r --;
                }
                if (left < r) {
                    quickSort(arr, left, r, orderByType);
                }

                if (right > l) {
                    quickSort(arr, l, right, orderByType);
                }
            }
        } else {
            while (l < r) {
                while (arr[l].compareTo(pivot) > 0) {
                    l ++;
                }

                while (arr[r].compareTo(pivot) < 0) {
                    r --;
                }

                if (l >= r) {
                    break;
                }

                // exchange
                swap(arr, l, r);

                if (arr[l].compareTo(pivot) == 0) {
                    r --;
                }

                if (arr[r].compareTo(pivot) == 0) {
                    l ++;
                }

                if (l == r) {
                    l ++;
                    r --;
                }
                if (left < r) {
                    quickSort(arr, left, r, orderByType);
                }

                if (right > l) {
                    quickSort(arr, l, right, orderByType);
                }
            }
        }
    }

    /**
     * 快速排序另一种方式实现
     * @param arr           要排序的数组
     * @param orderByType   升序还是降序 {@link OrderByTypeEnum}
     * @param <E>           数组的泛型
     */
    public static <E extends Comparable<E>> void quicklySort(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quicklySort(arr, 0, arr.length - 1, orderByType);
    }

    /**
     * 快速排序另一种方式实现的递归方法
     * @param arr
     * @param left
     * @param right
     * @param orderByType
     * @param <E>
     */
    private static <E extends Comparable<E>> void quicklySort(E[] arr, int left, int right, OrderByTypeEnum orderByType) {
        if (left >= right) {
            return;
        }
        int l = left, r = right;
        E pivot = arr[left];
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            while (l < r) {
                while (l < r && arr[r].compareTo(pivot) > 0) {
                    r --;
                }
                while (l < r && arr[l].compareTo(pivot) <= 0) {
                    l ++;
                }
                if (l < r) {
                    swap(arr, l, r);
                }
            }
        } else {
            while (l < r) {
                while (l < r && arr[r].compareTo(pivot) < 0) {
                    r --;
                }
                while (l < r && arr[l].compareTo(pivot) >= 0) {
                    l ++;
                }
                if (l < r) {
                    swap(arr, l, r);
                }
            }
        }
        swap(arr, l, left);
        quicklySort(arr, left, l - 1, orderByType);
        quicklySort(arr, l + 1, right, orderByType);
    }

    /**
     * 快速排序非递归实现
     * @param arr           要排序的数组
     * @param orderByType   排序方式（升序还是降序）
     * @param <E>           数组元素的泛型
     */
    public static <E extends Comparable<E>> void quickSortNonRecursion(E[] arr, OrderByTypeEnum orderByType) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSortNonRecursion(arr, 0, arr.length - 1, orderByType);
    }

    /**
     * 快速排序非递归实现
     * @param arr           要排序的数组
     * @param startIndex    开始索引
     * @param endIndex      结束索引
     * @param orderByType   排序方式（升序还是降序）
     * @param <E>           数组元素的泛型
     */
    private static <E extends Comparable<E>> void quickSortNonRecursion(E[] arr, int startIndex, int endIndex, OrderByTypeEnum orderByType) {
        // 用一个集合栈来代替递归的函数栈
        Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
        // 整个数列的起止下标，以哈希的形式入栈
        Map rootParam = new HashMap();
        rootParam.put("startIndex", startIndex);
        rootParam.put("endIndex", endIndex);
        quickSortStack.push(rootParam);
        // 循环结束条件：栈为空时结束
        while (!quickSortStack.isEmpty()) {
            // 栈顶元素出栈，得到起止下标
            Map<String, Integer> param = quickSortStack.pop();
            // 得到基准元素位置
            int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"), orderByType);
            // 根据基准元素分成两部分, 把每一部分的起止下标入栈
            if(param.get("startIndex") < pivotIndex -1){
                Map<String, Integer> leftParam = new HashMap<String, Integer>();
                leftParam.put("startIndex", param.get("startIndex"));
                leftParam.put("endIndex", pivotIndex -1);
                quickSortStack.push(leftParam);
            }
            if(pivotIndex + 1 < param.get("endIndex")){
                Map<String, Integer> rightParam = new HashMap<String, Integer>();
                rightParam.put("startIndex", pivotIndex + 1);
                rightParam.put("endIndex", param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }

    /**
     * 快速排序非递归实现
     * @param arr           要排序的数组
     * @param startIndex    开始索引
     * @param endIndex      结束索引
     * @param orderByType   排序方式（升序还是降序）
     * @param <E>           数组元素的泛型
     * @return              基准元素的索引
     */
    private static <E extends Comparable<E>> int partition(E[] arr, int startIndex, int endIndex, OrderByTypeEnum orderByType) {
        // 取第一个位置的元素作为基准元素
        E pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        if (orderByType == null || orderByType.equals(OrderByTypeEnum.ASC)) {
            while( left != right) {
                //控制right指针比较并左移
                while(left<right && arr[right].compareTo(pivot) > 0){
                    right--;
                }
                //控制right指针比较并右移
                while(left<right && arr[left].compareTo(pivot) <= 0) {
                    left++;
                }
                //交换left和right指向的元素
                if(left<right) {
                    swap(arr, left, right);
                }
            }
        } else {
            while( left != right) {
                //控制right指针比较并左移
                while(left<right && arr[right].compareTo(pivot) < 0){
                    right--;
                }
                //控制right指针比较并右移
                while(left<right && arr[left].compareTo(pivot) >= 0) {
                    left++;
                }
                //交换left和right指向的元素
                if(left<right) {
                    swap(arr, left, right);
                }
            }
        }
        //pivot和指针重合点交换
        swap(arr, startIndex, left);
        return left;
    }

    /**
     * 交换数组两个索引位置的元素
     * @param arr   数组
     * @param i     要交换位置的一个索引
     * @param j     要交换位置的两个索引
     * @param <E>   泛型
     */
    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
